#include<stdio.h>
#include<stdlib.h>

int number;		// numarul de operatii ce se vor efectua (pop si push)

int nr_push;		// numarul de operatii de tip push
int nr_pop;	// numarul de operatii de tip pop;
int nr_cautari;	// numarul de cautari ce se vor efectua
int vec_pop[100000000];	// in acest vector se memoreaza valorile scoase de pe stiva
int vec_adaugari[100000000];	// in acest vector se memoreaza valorile adaugate
int vec_cautari[100000000];	// in acest vector se memoreaza valorile cautate

int loc_sp;			// memoreaza al catelea element a fost gasit un nod oarecare cautat pentru spaghetti
int loc_st;			// memoreaza al catelea element a fost gasit un nod oarecare cautat pentru stiva normala
int ok=0;	// este folosit la functia random pentru a specifica daca se cauta elemente deja scoase(ok=1) sau orice element(ok=0)
double timpara=0,timparb=0;	// variabile in care se memoreaza timpii

struct spaghetti
{
	int val;
	spaghetti *next;
};
spaghetti *head_sp;

struct stiva
{
	int val;
	stiva *next;
};
stiva *head_st;

struct history
{
	int adresa;
	history *next;
};
history *head_hi;

void push_history()		//adaugare in lista istorie
{
	if(head_sp == NULL)	// head_sp reprezinta capul stivei spaghetti, iar daca acesta este null se iese din functie
		return;

	history *nou=(history *)malloc(sizeof(history));	// alocam un nou nod
	nou->adresa=int(head_sp);		// facem cast pentru a putea salva adresa
	nou->next=head_hi;	// se adauga in capatul listei

	head_hi=nou;	// noul cap va fi nodul nou
	return;
}	  

int pop_sp( int *val)		// scoaterea elementului din stiva spaghetti
{
	if(head_sp == NULL)	// stiva spaghetti este goala
		return 0;

	push_history();		// nodul ce este scos i se memoreaza adresa in lista history
	*val=head_sp->val;		// valoarea ce este scoasa este trimisa prin referinta
	head_sp=head_sp->next;		// noul cap va fi urmatorul element din lista
	return 1;		// operatie efectuata cu succes
}
void push_sp(int val)		// adaugare in stiva spaghetti
{
	spaghetti *nou=(spaghetti *)malloc(sizeof(spaghetti));	//se aloca un nod nou
	nou->val=val;
	nou->next=head_sp;	// se adauga in capatul listei
	head_sp=nou;	// noul capat al listei este noul nod
}

int pop_st(int *val)		// scoaterea elementului din stiva normala
{
	if(head_st==NULL)		// stiva este goala
		return 0;

	stiva *x=head_st;	// se memoreaza nodul ce va fi scos
	*val=head_st->val;		// valoarea scoasa este trimisa prin referinta
	head_st=head_st->next;	//capul stivei va fi urmatorul element


	free(x);	// se elibereaza nodul memorat
	return 1;
}
void push_st(int val)		// adaugarea in stiva normala
{
	stiva *nou=(stiva *)malloc(sizeof(stiva));		// se aloca un nod nou
	nou->val=val;		
	nou->next=head_st;	// se adauga in caparul stivei
	head_st=nou;		// capul listei devine chiar nodul cel nou
}

int cautare_spaghetti(int val)	// se returneaza 1 daca se gaseste valoarea in lista istorie, 0 daca se gaseste pe stiva spaghetti si -1 daca nu se gaseste
{
	history *h=head_hi;	// un pointer cu care parcurgem lista istorie

	loc_sp=1;

	while(h != NULL)		// parcurgem lista istorie
	{
		if( ((spaghetti *)(h->adresa))->val == val )
			return 1;
		h=h->next;
		loc_sp++;
	}

	loc_sp=1;
	spaghetti *s=head_sp;	// acum cu ajutorul lui s parcurgem stiva spaghetti
	while(s!=NULL)
	{
		if(s->val == val )
			return 0;
		s=s->next;
		loc_sp++;
	}
	
	return -1;
}
int cautare_stiva_normala(int val)	// se returneaza 1 daca se gaseste pe stiva si 0 daca nu se gaseste pe stiva
{
	stiva *s=head_st;

	loc_st=1;
	while(s!=NULL)
	{
		if(s->val==val)
			return 1;
		s=s->next;
		loc_st++;
	}

	return 0;
}

void eliberare_structuri()	// se dezaloca stivele
{
	spaghetti *x=head_sp;
	while(head_sp!=NULL)
	{
		x=head_sp;
		head_sp=head_sp->next;
		free(x);
	}

	stiva *y=head_st;
	while(head_st!=NULL)
	{
		y=head_st;
		head_st=head_st->next;
		free(y);
	}

	history *z=head_hi;
	while(head_hi!=NULL)
	{
		z=head_hi;
		head_hi=head_hi->next;
		free(z);
	}

	head_hi=NULL;
	head_st=NULL;
	head_sp=NULL;
}

void random()		// functia random de efectuare a operatiilor
{
	int x;		// variabila ce va lua valori pentru cautare si pentru adaugare aleatorie
	int alegere;		// daca alegere={1,3,7} se face pop, iar in caz contrar push (alegere este un nr de la 0 la 9)
	nr_push=0;		// resetam numatul de operatii
	nr_pop=0;
	nr_cautari=0;

	LARGE_INTEGER t1,t2;		// ajuta la masurarea timpilor
	LARGE_INTEGER tickPerSecond;	// ajuta la masurarea timpilor
	_int64 t_st=0,t_sp=0;

	for( int i=0; i<number; i++)
	{
		alegere=rand()%10;	// ultima cifra a numarului ales random
		if( (alegere==1 || alegere==3 || alegere==7 ) && head_st!=NULL )	// in acest caz se face pop....avem conditie ca stiva sa nu fie goala
		{
			pop_st(&x);
			pop_sp(&x);
			vec_pop[nr_pop]=x;
			nr_pop++;
		}
		else
			if( (alegere==2 || alegere==5 || alegere==9 ) && head_st!=NULL) // se face o cautare din cifrele deja introduse, insa stiva trebuie sa contina ceva ( head_st!=NULL )
			{
				if(ok && nr_pop>0)
					x=vec_cautari[rand()%nr_pop];	// se alege un numar random din cele deja scoase (eliminate cand s-a facut pop)
				else
					x=vec_adaugari[rand()%nr_push];		// se alege un numar random din vector....stim cate elemente s-au adaugat (nr_push) asa ca restul impartirii unui nr random la numarul nostru ne va da un indice corespunzator

//------------------------------- aici vei face cronometrarea ----------------------------------------------
				QueryPerformanceCounter(&t1);
					cautare_spaghetti(x);		// se cauta in stiva spaghetti
				QueryPerformanceCounter(&t2);
				 t_sp=t_sp + (t2.QuadPart-t1.QuadPart);     

				QueryPerformanceCounter(&t1);
					cautare_stiva_normala(x);		// se cauta in stiva normala
				QueryPerformanceCounter(&t2);
				 t_st=t_st + (t2.QuadPart-t1.QuadPart);  
//==================================================================================================================
// ca informatii ai: numarul de operatii-number, numarul de cautari-nr_cautari, numarul de pop-uri= nr_pop
				// numarul de push-uri = nr_push, vectorul cu valorile inserate- vec_adaugari, vectorul cu valori cautate- vec_cautari
				// si vectorul cu valori scoase de pe stiva- vec_pop . le poti folosi pentru a scrie un mesaj la afisarea graficului cu timpii
				// ex.: numar operatii 122, numar pop 12 numar cautari 100 numar push 10 :) 
				// poti memora si intr-un fisier cei doi vectori :D
				vec_cautari[nr_cautari]=x;
				nr_cautari++;
			}
			else		// in acest caz se va efectua o adaugare ( push )
			{
				x=rand();		// se alege o valoare aleatorie
				push_sp(x);	// stiva spaghetti
				push_st(x);	// stiva normala
				vec_adaugari[nr_push]=x;
				nr_push++;
			}
	}
	QueryPerformanceFrequency(&tickPerSecond);
	timpara=(double)t_sp/(1000*((double)tickPerSecond.QuadPart/1000)); // timpul pentru spaghetii il salvez in variabila timpara
	QueryPerformanceFrequency(&tickPerSecond);
	timparb=(double)t_st/(1000*((double)tickPerSecond.QuadPart/1000)); // timpul pentru stiva normala il salvez in variabila timparb
	eliberare_structuri();
}



